package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * User: Ruijie Date: 2016/10/24
 * Given a collection of numbers that might contain duplicates, return all possible unique permutations.
 For example,
 [1,1,2]have the following unique permutations:
 [1,1,2],[1,2,1], and[2,1,1].
获取唯一的全排列
 */
public class PermutationsLi {
    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arr=new ArrayList<Integer>();
        boolean[] flag=new boolean[num.length];
        Arrays.sort(num);
        dfs(num,res,0,flag,arr);
        return res;
    }
    private static void dfs(int[] num, ArrayList<ArrayList<Integer>> res, int start, boolean[] flag,
                            ArrayList<Integer> arr) {
        if(start>=num.length){
            res.add(new ArrayList<>(arr));
        }else{
            for(int i=0;i<num.length;i++){
                if(!flag[i]){
                    flag[i]=true;
                    arr.add(num[i]);
                    dfs(num,res,start+1,flag,arr);
                    arr.remove(arr.size()-1);
                    flag[i]=false;
                    //如果出现重复则跳到下一个
                    while(i<num.length-1 && num[i]==num[i+1]) i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] num={1,1,2};
        ArrayList<ArrayList<Integer>> res=permuteUnique(num);
        System.out.println(res);
    }

}
